//<p>给定 <em>n</em> 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。</p>
//
//<p>求在该柱状图中，能够勾勒出来的矩形的最大面积。</p>
//
//<p> </p>
//
//<p><strong>示例 1:</strong></p>
//
//<p><img src="https://assets.leetcode.com/uploads/2021/01/04/histogram.jpg" /></p>
//
//<pre>
//<strong>输入：</strong>heights = [2,1,5,6,2,3]
//<strong>输出：</strong>10
//<strong>解释：</strong>最大的矩形为图中红色区域，面积为 10
//</pre>
//
//<p><strong>示例 2：</strong></p>
//
//<p><img src="https://assets.leetcode.com/uploads/2021/01/04/histogram-1.jpg" /></p>
//
//<pre>
//<strong>输入：</strong> heights = [2,4]
//<b>输出：</b> 4</pre>
//
//<p> </p>
//
//<p><strong>提示：</strong></p>
//
//<ul>
//	<li><code>1 <= heights.length <=10<sup>5</sup></code></li>
//	<li><code>0 <= heights[i] <= 10<sup>4</sup></code></li>
//</ul>
//<div><div>Related Topics</div><div><li>栈</li><li>数组</li><li>单调栈</li></div></div><br><div><li>👍 1958</li><li>👎 0</li></div>

package com.rising.leetcode.editor.cn;

/**
 * 柱状图中最大的矩形
 * @author DY Rising
 * @date 2022-05-27 16:35:27
 */
public class P84_LargestRectangleInHistogram{
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P84_LargestRectangleInHistogram().new Solution();
        //System.out.println(solution.largestRectangleArea(new int[]{2,1,5,6,2,3}));
        //System.out.println(solution.largestRectangleArea(new int[]{4,2}));
        System.out.println(solution.largestRectangleArea(new int[]{4,2,0,3,2,4,3,4}));
    }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) return 0;
        int n = heights.length;
        int[] left_i = new int[n];
        int[] right_i = new int[n];
        left_i[0] = -1;
        right_i[n - 1] = n;
        int res = 0;
        for (int i = 1; i < n; i++) {
            int tmp = i - 1;
            while (tmp >= 0 && heights[tmp] >= heights[i])
                tmp = left_i[tmp];
            left_i[i] = tmp;
        }
        for (int i = n - 2; i >= 0; i--) {
            int tmp = i + 1;
            if (tmp < n && heights[tmp] >= heights[i])
                tmp = right_i[tmp];
            right_i[i] = tmp;
        }
        for (int i = 0; i < n; i++)
            res = Math.max(res, (right_i[i] - left_i[i] - 1) * heights[i]);
        return res;
    }
}

//leetcode submit region end(Prohibit modification and deletion)

}
